package com.example.leetdemo.finash;

import java.util.HashMap;
import java.util.Map;

/**
 * LRU 艹
 */
public class Solution146 {


    public static void main(String[] args) {
        Solution146 solution146 = new Solution146(2);
        solution146.put(1, 1);
        solution146.put(2, 2);
        System.err.println(solution146.get(2));

        solution146.put(3, 3);
//        solution146.test();
        System.err.println(solution146.get(2));
//        solution146.test();
        solution146.put(4, 4);
        solution146.get(1);
        solution146.get(3);
        solution146.get(4);
        solution146.test();
//        solution146.get(1);
//        solution146.get(3);

    }

    private void test() {
        Node p = head;
        for (int i = 0; i < size; i++) {
            System.err.println(p.key + " " +  p.value);
            p = p.next;
        }
    }

    private int capacity;

    private Map<Integer, Node> map = new HashMap<>();

    private int size;
    private Node head;
    private Node end;

    public Solution146(int capacity) {
        this.capacity = capacity;
        this.size = 0;
    }

    public int get(int key) {
        Node p = map.get(key);
//        System.err.println(size);
        if (p != null) {
            Node nowFirst = p.first;
            Node nowNext = p.next;
            if (p == head) {
                return p.value;
            }
            if (p != end) {
                nowFirst.next = nowNext;
                nowNext.first = nowFirst;
                p.next = head;
                head.first = p;
                head = p;
            }
            if (p == end) {
                Node newEnd = p.first;
                head.first = p;
                p.next = head;
                head = p;
                newEnd.next = null;
                end = newEnd;
            }
            head.first = null;
            return head.value;
        }
        return -1;
    }

    public void put(int key, int value) {
        if (head == null) {
            Node newHead = new Node(key, value, null, null);
            head = newHead;
            end = newHead;
            size++;
            map.put(key, head);
            return;
        }
        Node p = map.get(key);
        if (p!= null) {
            Node nowFirst = p.first;
            Node nowNext = p.next;
            p.value = value;

            if (p != end && p != head) {
                nowFirst.next = nowNext;
                nowNext.first = nowFirst;
                p.next = head;
                head.first = p;
                head = p;
            }
            if (p == end && p != head) {
                Node newEnd = p.first;
                head.first = p;
                p.next = head;
                head = p;
                newEnd.next = null;
                end = newEnd;
            }
            return;
        }
        size++;
        if (size > capacity) {
            map.remove(end.key);
            Node newHead = new Node(key, value, null, head);
            head.first = newHead;
            head = newHead;
            Node newEnd = end.first;
            newEnd.next = null;
            end = newEnd;
            size--;
            map.put(key, newEnd);
        } else {
            Node node = new Node(key, value, null, head);
            head.first = node;
            head = node;
            map.put(key, node);
        }

    }

    class Node {
        Integer key;
        Integer value;
        Node first;
        Node next;
        Node(int key, int value) {
            this.key = key;
            this.value = value;
        }
        Node(int key, int value, Node first, Node next) {
            this.key = key;
            this.value = value;
            this.first = first;
            this.next = next;
        }
    }
}
